
public class MyTwoWayLinkedList {
    class ListNode {
        public int val;
        public ListNode next;  //next域, 存放后一个节点的地址
        public ListNode prev;  //prev域, 存放前一个节点的地址
        public ListNode(int val) {
            this.val = val;
        }
    }
    ListNode head; //头指针
    ListNode rear; //尾指针

    public void addLast(int val) {  //尾插
        ListNode newNode = new ListNode(val);
        if (head == null && rear == null) {
            head = rear = newNode;
        }
        rear.next = newNode;
        newNode.prev = rear;
        rear = newNode;
    }

    public void addFirst(int val) {  //头插
        ListNode newNode = new ListNode(val);
        if (head == null && rear == null) {
            head = rear = newNode;
            return;
        }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }

    public void addIndex(int index, int val) {  //插入到指定位置
        ListNode newNode  = new ListNode(val);
        if (head == null && rear == null && index == 0) {
            head = rear = newNode;
            return;
        }
        ListNode TargetNode = head;
        int stepCount = index;
        while (stepCount != 0) {
            TargetNode = TargetNode.next;
            stepCount--;
        }
        newNode.next = TargetNode;

        newNode.prev = TargetNode.prev;
        TargetNode.prev.next = newNode;

        TargetNode.prev = newNode;
    }

    public void removeLast() {  //尾删
        ListNode p = rear.prev;
        rear.prev.next = null;
        rear.prev = null;

        rear = p;
    }
    public void removeFirst() {  //头删
        ListNode p = head.next;
        head.next.prev = null;
        head.next = null;

        head = p;
    }
    public void removeIndex(int index) {  //删除指定位置的元素
        ListNode TargetNode = head;
        int stepCount = index;
        while(stepCount != 0) {
            TargetNode = TargetNode.next;
            stepCount--;
        }
        TargetNode.next.prev = TargetNode.prev;
        TargetNode.prev.next = TargetNode.next;

        TargetNode.next = null;
        TargetNode.prev = null;
    }
    public boolean removeKey(int data) {  //删除指定值的元素
        ListNode TargetNode = head;
        int flag = 0;
        while (TargetNode != null) {
            if (TargetNode.val == data) {
                if (TargetNode == head) {
                    removeFirst();
                    flag = 1;
                    TargetNode = TargetNode.next;
                    continue;
                }
                if (TargetNode == rear) {
                    removeLast();
                    flag = 1;
                    TargetNode = TargetNode.next;
                    continue;
                }
                ListNode TargetNextNode =TargetNode.next;

                TargetNode.next.prev = TargetNode.prev;
                TargetNode.prev.next = TargetNode.next;

                TargetNode = TargetNextNode;

                flag = 1;
            }
            TargetNode = TargetNode.next;
        }

        if (flag == 1) {  //删除成功
            return true;
        }else {
            System.out.println("不存在该值");
            return false;
        }
    }
    public boolean contains(int val) {
        ListNode p = head;
        while (p != null) {
            if (p.val == val) {
                return true;
            }
            p = p.next;
        }
        return false;
    };
    public boolean isEmpty() {
        if (head == null && rear == null) {
            return true;
        }
        return false;
    };
    public void clear() {
        head = rear = null;
    };

    @Override
    public String toString() {
        String str = "";
        ListNode p = head;
        while(p != null) {
            if (p == head){
                str += "[";
                str += head.val;
                str += ",";
                p = p.next;
                continue;
            }
            if (p == rear) {
                str += rear.val;
                str += "]";
                p = p.next;
                continue;
            }
            str += p.val;
            str += ",";
            p = p.next;
        }
        return str;
    }
}
